Polinomios

Para empezar a trabajar con polinomios, tenemos que especificar las variables y qué anillo de coeficientes vamos a considerar. gap por defecto expande las expresiones que introducimos.

InstallMethod(ViewString,[IsPolynomial],String);

Para definir una indeterminada, utilizamos Intederminate, indicando el nombre con el que se va a representar (en este caso x) y sobre qué anillo se va a definir esa indeterminada (en este caso el cuerpo de los racionales).

x:=Indeterminate(Rationals,"x");

La indeterminada se mostrará en la salida como “x”, y en nuestro caso hemos usado también ese nombre como identificador para poder operar con esa indeterminada.

gap expandirá cualquier expresión polinomial que le pasemos.

(x+1)*(x-1)^5;

x^6-4*x^5+5*x^4-5*x^2+4*x-1

Si queremos obtener una lista de los coeficientes de un polinomio en una variable, podemos usar lo siguiente.

CoefficientsOfUnivariatePolynomial(x^3+x-1);

[ -1, 1, 0, 1 ]

Y el coeficiente líder lo obtenemos con LeadingCoefficient.

LeadingCoefficient(x^3+x-1);

Definamos una función para encontrar el término líder de un polinomio respecto de una variable. En ella usamos funciones que son alternativa a las que acabamos de ver para más de una variable.

terminolider:=function(p,x)
    local grado;
    grado:=DegreeIndeterminate(p,x);
    return PolynomialCoefficientsOfPolynomial(p,x)[grado+1]*x^grado;
end;

function( p, x ) ... end

terminolider(x^2+x-1,x);

x^2

terminolider(3*x^2+x-1,x);

3*x^2

La función que hemos definido se puede utilizar con polinomios en más de una variable.

y:=Indeterminate(Rationals,"y");

terminolider(y*x^2+y^4*x-1,x);

x^2*y

terminolider(y*x^2+y^4*x-1,y);

x*y^4

LeadingCoefficient(y*x^2+y^4*x-1);

PolynomialCoefficientsOfPolynomial(y*x^2+y^4*x-1,x);

[ -1, y^4, y ]

División de polinomios

Si el anillo de coeficientes que consideramos es un cuerpo, entonces sabemos que el anillo de polinomios sobre una sola variable es un dominio euclídeo. Por tanto, podemos usar las funciones que ya conocemos para calcular el cociente y resto de una división.

QuotientRemainder(x^3-x+1,2*x^2-3);

[ 1/2*x, 1/2*x+1 ]

Si nuestro anillo de polinomios no es un dominio euclídeo, entonces no podemos usar estas funciones.

QuotientRemainder((x^3-x+1)*(y-1),y-1);

Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 2nd choice method found for `QuotientRemainder' on 3 arguments at /home/pedro/lib/gap-4.12.2/lib/methsel2.g:249 called from
QuotientRemainder( DefaultRing( [ r, m ] ), r, m ) at /home/pedro/lib/gap-4.12.2/lib/ring.gi:1092 called from
<function "QuotientRemainder for two ring elements">( <arguments> )
 called from read-eval loop at stream:1

Ahora bien, si que podemos usar la función Quotient que nos da el cociente, en caso de que éste pertenezca a nuestro anillo de polinomio, y fail en caso contrario.

Quotient((x^3-x+1)*(y-1),y-1);

x^3-x+1

Podemos utilizar también /. En el caso en que el denominador divida al numerador, gap devolverá el cociente. En caso contrario, la salida será una función racional.

(x^3-x+1)*(y-1)/(y-1);

x^3-x+1

(x^3-x+1)*(y-1)/(y-14);

(x^3*y-x^3-x*y+x+y-1)/(y-14)

Factorización de polinomios

Si lo que queremos es factorizar polinomios, primero tenemos que definir la variable, e indicar cuál es el anillo de coeficientes para nuestros polinomios. Luego se usa Factors igual que con enteros.

x:=Indeterminate(ZmodnZ(5),"x");

TeachingMode();

#I  Teaching mode is turned OFF

Factors(x^2+1);

[ x+Z(5), x+Z(5)^3 ]

Usamos el modo enseñanza (TeachingMode) para visualizar mejor los elmeentos de \(\mathbb{Z}_5\).

TeachingMode(true);

#I  Teaching mode is turned ON

Factors(x^2+1);

[ x+ZmodnZObj(2,5), x+ZmodnZObj(3,5) ]

x:=Indeterminate(Rationals,"x");

Factors(x^2+1);

[ x^2+1 ]

Lo mismo ocurre con las raices y con el hecho de ser irreducible.

x:=Indeterminate(ZmodnZ(3),"x");

RootsOfUPol(x^3-1);

[ ZmodnZObj(1,3), ZmodnZObj(1,3), ZmodnZObj(1,3) ]

RootsOfUPol(x^3-1);

[ ZmodnZObj(1,3), ZmodnZObj(1,3), ZmodnZObj(1,3) ]

IsIrreducible(x^2+1);

true

x:=Indeterminate(ZmodnZ(2),"x");

IsIrreducible(x^2+1);

false

Veamos ahora a modo de ejemplo cómo calcular todos los polinomios irreducibles hasta un determinado grado en un anillo finito. Empezamos definiendo una función que nos genere todos los polinomios hasta un determinado grado.

polshastagradomodm:=function(n,x)
    local ps, R;
    
    R:=CoefficientsRing(DefaultRing(x));
    if Size(R)=infinity then
        return fail;
    fi;
    
    if (n=0) then
        return Elements(R);
    fi;

    ps:=polshastagradomodm(n-1,x);
    return Set(Cartesian(ps,x^n*Elements(R)),Sum);
end;

function( n, x ) ... end

Así todos los polinomios en \(\mathbb{Z}_3\) de grado menor o igual que dos son:

x:=Indeterminate(ZmodnZ(3),"x");

polshastagradomodm(2,x);

[ ZmodnZObj(0,3), ZmodnZObj(1,3), -ZmodnZObj(1,3), x, x+ZmodnZObj(1,3),   x-ZmodnZObj(1,3), -x, -x+ZmodnZObj(1,3), -x-ZmodnZObj(1,3), x^2,   x^2+ZmodnZObj(1,3), x^2-ZmodnZObj(1,3), x^2+x, x^2+x+ZmodnZObj(1,3),   x^2+x-ZmodnZObj(1,3), x^2-x, x^2-x+ZmodnZObj(1,3), x^2-x-ZmodnZObj(1,3),   -x^2, -x^2+ZmodnZObj(1,3), -x^2-ZmodnZObj(1,3), -x^2+x,   -x^2+x+ZmodnZObj(1,3), -x^2+x-ZmodnZObj(1,3), -x^2-x, -x^2-x+ZmodnZObj(1,3),  -x^2-x-ZmodnZObj(1,3) ]

De entre ellos podemos escoger los que son irreducibles.

Filtered(polshastagradomodm(2,x), IsIrreducible);

[ x, x+ZmodnZObj(1,3), x-ZmodnZObj(1,3), -x, -x+ZmodnZObj(1,3),   -x-ZmodnZObj(1,3), x^2+ZmodnZObj(1,3), x^2+x-ZmodnZObj(1,3),   x^2-x-ZmodnZObj(1,3), -x^2-ZmodnZObj(1,3), -x^2+x+ZmodnZObj(1,3),   -x^2-x+ZmodnZObj(1,3) ]

Y si queremos quedarnos con un representante salvo asociados, podemos usar lo siguiente.

Set(Filtered(polshastagradomodm(2,x), IsIrreducible), StandardAssociate);

[ x, x+ZmodnZObj(1,3), x-ZmodnZObj(1,3), x^2+ZmodnZObj(1,3),   x^2+x-ZmodnZObj(1,3), x^2-x-ZmodnZObj(1,3) ]

Cociente por un ideal. Cuerpos finitos

Intentemos calcular los divisores de cero y unidades del anillo cociente \(R=\mathbb{Z}_2[x]/(x^2+1)\). Empezamos definiendo nuestra variable y el módulo.

 x:=Indeterminate(ZmodnZ(2),"x");

modulo:=x^2+1;

x^2+ZmodnZObj(1,2)

Definimos \(\mathbb{Z}_2[x]\), y luego hacemos el cociente por el ideal generado por modulo.

P:=PolynomialRing(ZmodnZ(2),"x");

GF(2)[x]

R:=P/Ideal(P,[modulo]);

<ring GF(2),(1),(x)>

Elements(R);

[ 0*(1), (x), (1), (1)+(x) ]

R es un anillo, y como tal podemos preguntarnos quién es su elemento neutro para la suma y para el producto.

Zero(R);

0*(1)

One(R);

(1)

También podemos calcular el grupo de unidades de este anillo.

Units(R);

<group with 1 generator>

Elements(Units(R));

[ (x), (1) ]

Tenemos otra forma alternativa de hacer cocientes, que además nos permite hacer operaciones más fácilmente en el cociente.

g:=NaturalHomomorphismByIdeal(P,Ideal(P,[modulo]));

[ x, ZmodnZObj(1,2) ] -> [ (x), (1) ]

R:=Image(g);

<ring GF(2),(1),(x)>

Image(g,x^2+x);

(1)+(x)

clasex:=Image(g,x);

(x)

clasex^2+clasex;

(1)+(x)

PreImagesRepresentative(g,clasex^2);

ZmodnZObj(1,2)

Si nuestro polinomio es irreducible, también podemos utilizar AlgebraicExtension.

f:=x^2+x+1;

x^2+x+ZmodnZObj(1,2)

S:=AlgebraicExtension(ZmodnZ(2),f);

<field of size 4>

En gap podemos usar cualquier cuerpo finito con el comando GF.

K:=GF(9);

GF(3^2)

Size(K);

GeneratorsOfField(K);

[ Z(9)^1 ]

Elements(K);

[ ZmodnZObj(0,3), ZmodnZObj(1,3), ZmodnZObj(2,3), Z(9)^1, Z(9)^2, Z(9)^3,   Z(9)^5, Z(9)^6, Z(9)^7 ]

GF(2^8);

GF(2^8)